package com.sakura.二叉树;

import java.util.*;

public class Code102_二叉树的层序遍历 {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    // 此题不推荐
    public List<List<Integer>> levelOrder_1(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root != null) {
            Queue<TreeNode> queue = new LinkedList<>();
            HashMap<TreeNode, Integer> levels = new HashMap<>();
            queue.offer(root);
            levels.put(root, 0);
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                int level = levels.get(cur);

                if (ans.size() == level) {
                    ans.add(new ArrayList<>());
                }
                ans.get(level).add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                    levels.put(cur.left, level + 1);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                    levels.put(cur.right, level + 1);
                }
            }
        }
        return ans;
    }

    public static final int MAX_LEN = 2001;

    public static TreeNode[] queue = new TreeNode[MAX_LEN];

    public static int l, r;

    // 此方法为每次处理一层的优化bfs，此题推荐
    public List<List<Integer>> levelOrder_2(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();

        if (root != null) {
            l = r = 0;
            queue[r++] = root;
            while (l < r) {
                int size = r - l;
                ArrayList<Integer> list = new ArrayList<>();
                for (int i = 0; i < size; i++) {
                    TreeNode cur = queue[l++];
                    list.add(cur.val);
                    if (cur.left != null) {
                        queue[r++] = cur.left;
                    }
                    if (cur.right != null) {
                        queue[r++] = cur.right;
                    }
                }
                ans.add(list);
            }
        }

        return ans;
    }

}
